package easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Test {

  public static void main(String[] args) {
  }


//  102.二叉树的层序遍历
  List<List<Integer>> list = new ArrayList<>();

  public List<List<Integer>> levelOrder(TreeNode root) {
    dns(root,0);
    return list;
  }

  public void dns(TreeNode root,int lever){
    if (root == null){
      return;
    }
    if (list.size() == lever){
      list.add(new ArrayList<Integer>());
    }
    list.get(lever).add(root.val);
    dns(root.left,lever + 1);
    dns(root.right, lever + 1);
  }

//  110.平衡二叉树
public boolean isBalanced(TreeNode root) {
  if(root == null){
    return true;
  }
  return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

  public int height(TreeNode root) {
    if(root == null) return 0;
    return Math.max(height(root.left),height(root.right)) + 1;
  }

//  3. 无重复字符的最长子串
  public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    if (s.length() == 1) return 1;
    HashSet<Character> set = new HashSet<>();
    int res = 0;
    for (int i = 0; i < s.length(); i++) {
      for (int j = i; j < s.length(); j++) {
        char c = s.charAt(j);
        if (!set.contains(c)){
          set.add(c);
        }else {
          if (set.size() >res){
            res = set.size();
          }
          set.clear();
          break;
        }
      }
    }
    return res;
  }

  class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
       TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
